﻿'''
763 划分字母区间 贪心
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
提示：
1 <= s.length <= 500
s 仅由小写英文字母组成
'''
class Solution(object):
    def partitionLabels(self, s: str) -> list[int]:
        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] = i     #遍历字符串获得每个字符的最右下标
        left, right = 0, 0
        result = []
        for i in range(len(s)):
            right = max(right, count[ord(s[i]) - ord('a')]) #遍历字符串不断更新当前字符串最右下标范围
            if i == right:      #当当前下标到达最右下标时，说明可以划分一段
                result.append(right - left + 1)
                left = i + 1
        return result
#示例
if __name__ == '__main__':
    s = "ababcbacadefegdehijhklij"
    s1 = "eccbbbbdec"
    s2= "eccbbbbdecafghf"
    print(Solution().partitionLabels(s))
    print(Solution().partitionLabels(s1))
    print(Solution().partitionLabels(s2))


